package 优先算法.递归_搜索与回溯.初学递归.合并两个有序链表;

/**
 *https://leetcode.cn/problems/merge-two-sorted-lists/description/
 */
public class Main {

}
class Solution {
    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        if(list1.val <= list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list2.next,list1);
            return list2;
        }
    }

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
         list1.next = new ListNode(2);
         list1.next.next = new ListNode(4);
        ListNode list2 = new ListNode(1);
        list2.next = new ListNode(3);
        list2.next.next = new ListNode(4);
        Solution so = new Solution();
        ListNode Head = so.mergeTwoLists(list1, list2);
        ListNode cur = Head;
        while(cur != null){
            System.out.print(cur.val + "");
            cur = cur.next;
        }
    }
}
